#include<stdio.h>
#include<stdlib.h>
#include<stack>
#include<queue>

using namespace std;
typedef struct atreeNode
{
    int data;
    int h;
    struct atreeNode* left, *right;
}treeNode,*PTN;

//iterative遍历 前中后
void PreOrder_Iterative(treeNode *root);
void PostOrder_Iterative(treeNode *root);
void InOrder_Iterative(treeNode *root);
void levelOrder(treeNode *root);

//AVL树
int max(int a,int b){
    return a>b?a:b;
}
int height(treeNode *root);
treeNode *newNode(int val);
int getBalanceFactor(treeNode *node);
treeNode *rightRotate(treeNode *y);
treeNode *leftRotate(treeNode *y);
treeNode *insert(treeNode* node, int val);

int main(){
    treeNode* root = NULL;
	int array[6] = { 10,20,30,40,50,25};
	for (int i = 0;i < 6;i++)
	{
		root=insert(root, array[i]);
	}
    /*
     * 树的结构如下:
           30
        /      \
      20       40
     /  \        \
    10   25       50
    */ 
    printf("前序遍历（迭代版）:");
    PreOrder_Iterative(root);
    printf("\n后序遍历（迭代版）:");
    PostOrder_Iterative(root);
    printf("\n中序遍历（迭代版）:");
    InOrder_Iterative(root);
    printf("\n层次遍历:");
    levelOrder(root);
    return 0;
}

//辅助函数：计算树的高度
int height(treeNode *root){
    if(root==NULL)
        return 0;
    return 1+max(height(root->left),height(root->right));
}
//辅助函数：创建新节点
treeNode *newNode(int val){ 
    treeNode *node=(treeNode *)malloc(sizeof(struct atreeNode));
    node->data=val;
    node->h=0;
    node->left=NULL;
    node->right=NULL;
    return node;
}
//辅助函数：获取节点的平衡因子
int getBalanceFactor(treeNode *node){
    if(node==NULL)
        return 0;
    return height(node->left)-height(node->right);
}
//右旋
treeNode *rightRotate(treeNode *y){
    /*
     * 树的结构示意图
            y node
           / \
          x   0
         / \
    val 0+1 0
    */
    treeNode *x=y->left;
    treeNode *xr=x->right;
    // 右旋
    x->right=y;
    y->left=xr;
    // 更新结点高度
    x->h=height(x);
    y->h=height(y);
    //返回平衡后的结点
    return x;

}
//左旋
treeNode *leftRotate(treeNode *y){
    /*
     * 树的结构示意图
            y node
           / \
          0   x
             / \
            0   0+1 val
    */
   treeNode *x=y->right;
   treeNode *xl=x->left;
    // 左旋
    x->left=y;
    y->right=xl;

    x->h=height(x);
    y->h=height(y);
   //返回旋转后的根节点
   return x;
}
/*
*@brief 向以node为根节点的树中插入val
*
*@param node根节点
*@param val 待插入的值
*@param treeNode* 插入后该树新的根节点
*/
treeNode *insert(treeNode* node, int val)
{
	if(node==NULL)
        return newNode(val);
    if(val<node->data)
        node->left=insert(node->left,val);
    if(val>node->data)
        node->right=insert(node->right,val);
    //计算每个节点的h
    node->h=height(node);
    int bf=getBalanceFactor(node);//得到每个结点的平衡因子bf
    // LL
    if(bf>1&&val<node->left->data){
        return rightRotate(node);
    }
    // RR
    if(bf<-1&&val>node->right->data){
        return leftRotate(node);
    }
    // LR
    if(bf>1&&val>node->left->data){
        node->left=leftRotate(node->left);//先最小不平衡子树的左孩子左旋
        return rightRotate(node);//再将新树通过node右旋
    }
    // RL
    if(bf<-1&&val<node->right->data){
        node->right=rightRotate(node->right);
        return leftRotate(node);
    }
    return node;
}
/*
* 非递归先序遍历
* 借助栈实现
*/
void PreOrder_Iterative(treeNode *root){
    if(NULL==root){
        printf("空树一棵！");
        return; //空树
    }
    stack<treeNode *> nodeStack;
    nodeStack.push(root);
    while(!nodeStack.empty()){//栈非空
        treeNode *node = nodeStack.top();//保存栈顶结点
        printf("%d ",node->data);//访问栈顶元素
        nodeStack.pop();//删除栈顶元素
        //删除元素的右左孩子入栈
        if(node->right) nodeStack.push(node->right);
        if(node->left) nodeStack.push(node->left);   
    }

}
/*
* 非递归中序遍历
* 借助栈实现,curNode指针
*/
void InOrder_Iterative(treeNode *root){
    if(NULL==root)
        return;//空树
    stack<treeNode *>nodeStack;
    PTN curNode=root;//维护一个当前节点指针
    //当前节点指针非空，或栈非空时迭代处理
    while(curNode||!nodeStack.empty()){
        //当前节点非空，沿着左子树方向入栈
        while(curNode){
            nodeStack.push(curNode);
            curNode=curNode->left;
        }
        //此时栈顶没有左子树，或者左子树已经访问完
        curNode=nodeStack.top();//取栈顶节点
        printf("%d ",curNode->data);//访问栈顶节点
        nodeStack.pop();//从栈中删除被访问元素
        curNode=curNode->right;//当前节点设为右节点
    }
}
/*
* 非递归后序遍历
* 先序：根 左 右 
* 后序：左 右 根
* 通过对先序遍历时左右孩子入栈顺序进行调整（先左孩子入栈再右孩子入栈得到 "根右左"的遍历序列），将结果在通过一遍栈可以得到后序遍历。
* 借助两个栈实现
*/
void PostOrder_Iterative(treeNode* root){
    if(NULL==root)
        return ;
    stack<treeNode*> nodeStack;
    stack<treeNode*> resStack;
    nodeStack.push(root);
    while(!nodeStack.empty()){
        treeNode *node=nodeStack.top();//保存栈顶节点，便于寻找左右孩子
        //printf("%d ",node->data);
        resStack.push(node);
        nodeStack.pop();
        if(node->left) nodeStack.push(node->left);
        if(node->right) nodeStack.push(node->right); 
    }
    while(!resStack.empty()){
        printf("%d ",resStack.top()->data);
        resStack.pop();
    }
}
/*
* 借助队列
*/
void levelOrder(treeNode *root){
    if(NULL==root) 
        return;
    queue<treeNode *> nodeQueue;
    nodeQueue.push(root);
    while(!nodeQueue.empty()){
        treeNode *node=nodeQueue.front();
        printf("%d ",node->data);
        if(node->left) nodeQueue.push(node->left);//先进先出
        if(node->right) nodeQueue.push(node->right);
        nodeQueue.pop();
    }
}